package codetop.microsoft.T31;

import java.util.Arrays;

/**
 * @Author: 18362
 * @Create: 2022-08-15 0:17:05 星期一
 */
class Solution {
    public void nextPermutation(int[] nums) {
        if (nums.length == 1)
            return;
        int p = nums.length-2;
        while (p >= 0) {
            if (nums[p] < nums[p+1])
                break;
            p--;
        }
        if (p < 0) {
            Arrays.sort(nums);
            return;
        }
        for (int i=nums.length-1; i>=0; --i) {
            if (nums[i] > nums[p]) {
                int temp = nums[p];
                nums[p] = nums[i];
                nums[i] = temp;
                break;
            }
        }
        int left = p + 1, right = nums.length-1;
        while (left < right) {
            int temp = nums[left];
            nums[left++] = nums[right];
            nums[right--] = temp;
        }
    }
}